#define _CRT_SECURE_NO_WARNINGS 1

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
};
*/

class Solution
{
public:
    Node* flatten(Node* head)
    {
        Node* prev = nullptr;
        _flatten(head, prev);
        return head;
    }

private:
    void _flatten(Node* start, Node*& prev)
    {
        // if(prev != nullptr)
        // {
        //     start->prev = prev;
        //     prev->next = start;
        //     prev->child = nullptr;
        // }

        Node* cur = start;
        while (cur)
        {
            if (prev != nullptr)
            {
                prev->next = cur;
                cur->prev = prev;
                prev->child = nullptr;
            }

            prev = cur;
            Node* next = cur->next;

            if (cur->child != nullptr)
            {
                _flatten(cur->child, prev);
            }

            cur = next;
        }
    }
};